package com.leetcodecn.progrems;


public class AddTwoNumbers_002 {
    public static void main(String[] args) {
        // 数字为倒序
        /*
        最终测试用例，直接给我干碎，T-T
        [9]
        [1,9,9,9,9,9,9,9,9,9]
        连续进位的问题没有解决导致的错误
         */

        int[] l1 = new int[]{9};
        int[] l2 = new int[]{1, 9, 9, 9, 9, 9, 9, 9, 9, 9};


        ListNode ln1 = new ListNode(0);
        ListNode ln2 = new ListNode(0);
        ListNode temp1 = ln1;
        ListNode temp2 = ln2;

        for (int i : l1) {
            temp1.next = new ListNode(i);
            temp1 = temp1.next;
        }
        for (int i : l2) {
            temp2.next = new ListNode(i);
            temp2 = temp2.next;
        }


        System.out.println("================================================");

        ListNode res = addtwoNumbers(ln1.next, ln2.next);
        System.out.println(res.toString());
    }

    public static ListNode addtwoNumbers(ListNode l1, ListNode l2) {
        ListNode res = new ListNode(0);
        ListNode restemp = res;
        int sum = 0;
        int value1 = 0;
        int value2 = 0;
        //进位记录值
        int carrybit = 0;

        // l1 l2 有值，存在进位，则继续
        while (l1!=null || l2!=null || carrybit!=0) {
            value1 = l1 != null ? l1.val : 0;
            value2 = l2 != null ? l2.val : 0;

            //进位，当1+2>=10时，进位=1;当1，2都为0时，进位值=1，最后执行的这一次sum计算，使sum进到了更高位
            sum = value1 + value2 + carrybit;
            carrybit = sum/10;

            //每次都将数字直接插入到ListNode中
            restemp.next = new ListNode(sum%10);
            restemp = restemp.next;

            if (l1 != null) { l1 = l1.next; }
            if (l2 != null) { l2 = l2.next; }
        }

        return res.next;
    }

}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }


    @Override
    public String toString() {
        return ""+val + next;
    }
}

/*
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。
每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 

上面是链表的定义，那么我们用通俗点的语言来说就是：
一些节点，除了最后一个节点以外的每一个节点都存储着下一个节点的地址，依据这种方法依次连接， 构成一个链式结构。
 
在Java中我们需要自己定义一个链表的类来生成对象，这个类需要由一个存储数据的数据域也需要有存储下一个节点地址的域，因此，我们至少定义两个属性

 */